package string.leetcode_20;

import java.util.Deque;
import java.util.LinkedList;

public class StackSolution {
    public boolean isValid(String s) {
        int length = s.length();
        if(length % 2 == 1){
            return false;
        }
        Deque<Character> stack = new LinkedList<>();
        for(int i = 0; i < length; i++){
            char ch = s.charAt(i);
            if(ch == '('){
                stack.push(')');
            }else if(ch == '{'){
                stack.push('}');
            }else if(ch == '['){
                stack.push(']');
            }else if(stack.isEmpty() || ch != stack.pop()){
                return false;
            }
        }
        return stack.isEmpty();
    }
}
